package Day010_排序算法_异常.demo02_二分查找;

/*
    普通查找:
        原理：遍历数组，获取每一个元素，然后判断当前遍历的元素是否和要查找的元素相同，如果相同就返回该元素的
        索引。如果没有找到，就返回一个负数作为标识(一般是-1)
    二分查找:
        原理: 每一次都去获取数组的中间索引所对应的元素，然后和要查找的元素进行比对，如果相同就返回索引；
        如果不相同，就比较中间元素和要查找的元素的值；
        如果中间元素的值大于要查找的元素，说明要查找的元素在左侧，那么就从左侧按照上述思想继续查询(忽略右侧
        数据)；
        如果中间元素的值小于要查找的元素，说明要查找的元素在右侧，那么就从右侧按照上述思想继续查询(忽略左侧
        数据)；

    二分查找对数组是有要求的,数组必须已经排好序

    结论:
        中间元素的索引= (左索引+右索引)/2
        如果arr[mid] < 要查找的数,说明数据在右侧
        那么左索引 = mid+1
        如果arr[mid] > 要查找的数,说明数据在左侧
        那么右索引 = mid-1
        结束查找:左索引left > 右索引right
 */

public class Test {
    public static void main(String[] args) {
        //查找50
        int num = 50;
        int[] arr = {12, 25, 35, 50, 70};
        //定义变量index
        int index = -1;
        //定义变量,记录左索引,右索引
        int left = 0;
        int right = arr.length - 1;
        //查找
        while (left <= right) {
            //计算中间索引
            int mid = (left + right) / 2;
            //判断中间索引的元素与要查找的元素
            if (arr[mid] > num) {
                right = mid - 1;
            } else if (arr[mid] < num) {
                left = mid + 1;
            } else {
                index = mid;
                break;
            }
        }
        if (index == -1) {
            System.out.println("没有找到");
        } else {
            System.out.println("找到了,索引为:" + index);
        }
    }
}
